package com.fantaike.algorithm.sort;

/**
 * 归并算法：归并算法是将一个数组尽可能的拆分成元素相等的两个子组，之后继续对子组进行拆分
 * 直到子组的元素个数为1为止。拆分后会对相邻的子组进行有序的合并，直到合并成一个有序的数组为止
 * @author jishushen
 * @create 2021-08-07 16:49
 */
public class Merge {

    //辅助数组
    private static Comparable[] assist;

    /**
     * 对数组内的元素进行排序
     * @param array
     * @Date: 2021/8/7 16:52
     * @Author: xuepeng
     * @Return
     * @Throws
     */
    public static void sort(Comparable[] array){
        //1.初始化辅助数组assist
        assist = new Comparable[array.length];
        //2.定义一个lo变量和hi变量分别记录数组中最小索引和最大索引
        int lo = 0;
        int hi = array.length - 1;
        //3.调用sort重载方法完成array数组从索引lo到索引hi的元素进行排序
        sort(array,lo,hi);
    }

    /**
     * 对array数组中从索引lo到索引hi之间的元素进行排序
     * @param array
     * @param lo 开始索引
     * @param hi 结束索引
     * @Date: 2021/8/7 16:53
     * @Author: xuepeng
     * @Return
     * @Throws
     */
    private static void sort(Comparable[] array,int lo,int hi){
        //做一个安全校验
        if (hi <= lo){
            return;
        }
        //对lo到hi之间的数据进行拆分，找到中间索引
        int mid = lo + (hi - lo) / 2;  //5 9  则mid = 7
        //分别对每一组数据进行排序
        sort(array,lo,mid);
        sort(array,mid + 1,hi);

        //再把两个数组中的元素进行归并
        merge(array,lo,mid,hi);

    }


    /**
     * 判断v是否小于w
     * @param v
     * @param w
     * @Date: 2021/8/7 17:05
     * @Author: xuepeng
     * @Return
     * @Throws
     */
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w) < 0;
    }

    /**
     * 交换array数组中索引i和索引j处的数据
     * @param array
     * @param i
     * @param j
     * @Date: 2021/8/7 17:06
     * @Author: xuepeng
     * @Return
     * @Throws
     */
    private static void exch(Comparable[] array,int i,int j){
        Comparable temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 从索引lo到索引mid为一个子组，从索引mid+1到索引hi为另一个子组，把数组array中的这两个子组
     * 的数据合并成一个有序的大组（从索引lo到索引hi）
     * @param array
     * @param lo
     * @param mid
     * @param hi
     * @Date: 2021/8/7 17:01
     * @Author: xuepeng
     * @Return
     * @Throws
     */
    private static void merge(Comparable[] array,int lo,int mid,int hi){
        //定义三个指针
        int i = lo;
        int p1 = lo;
        int p2 = mid + 1;
        //遍历，移动p1指针和p2指针，比较对应索引处的值，找出小的那一个，放到辅助数组的索引对应处
        while (p1 <= mid && p2 <= hi){
            //比较对应索引处的值
            if (less(array[p1],array[p2])){
                assist[i++] = array[p1++];
            }else {
                assist[i++] = array[p2++];
            }
        }
        //遍历，如果p1指针没有走完，那么顺序移动p1指针，把对应元素放到辅助数组的对应索引处
        while (p1 <= mid){
            assist[i++] = array[p1++];
        }
        //遍历，如果p2指针没有走完，那么属顺序移动p2指针，把对应元素放到辅助数组的对应索引处
        while (p2 <= hi){
            assist[i++] = array[p2++];
        }
        //把辅助数组中的元素拷贝到原数组中
        for (int index = lo; index<= hi; index++){
            array[index] = assist[index];
        }
    }
}
